import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;


public class LLGenerator {

	String filename;
	HashMap<String, ArrayList<String[]>> rules;
	HashMap<String, HashSet<String>> firstSet;
	HashMap<String, HashSet<String>> followSet;
	HashMap<String, HashMap<String, String[]>> parseTable; //Indexed nonterminal -> terminal -> rule
	String firstNonTerminal;
	public LLGenerator(String filename) throws IOException{
		this.filename = filename;
		rules = new HashMap<String, ArrayList<String[]>>();
		firstSet = new HashMap<String, HashSet<String>>();
		followSet = new HashMap<String, HashSet<String>>();
		generateRules();
		generateFirstSet();
		generateFollowSet();
		generateParsingTable();

	}

	public void generateFollowSet(){

		Iterator<String> it = rules.keySet().iterator();
		
		/* Stubbed out for including $ in the follow sets
		followSet.put(firstNonTerminal, new HashSet<String>());
		followSet.get(firstNonTerminal).add("$");
		*/

		while (it.hasNext()){

			String currNonTerm = it.next();

			ArrayList<String[]> currRules = rules.get(currNonTerm);

			for(int aNdx = 0; aNdx < currRules.size(); aNdx++ ){
				String[] cRule = currRules.get(aNdx);

				for (int rNdx = 0 ; rNdx < cRule.length; rNdx++){
					String term = cRule[rNdx];

					if (isNT(term)){

						String put;

						if (rNdx == cRule.length-1){
							put = currNonTerm;
							insertFollowSet(term, put);
							if (term.equals("<bin-op>"))
								System.out.println("Here");
						}
						else{
							put = cRule[rNdx+1];

							if (!isNT(put)){
								insertFollowSet(term, put);
								if (term.equals("<bin-op>"))
									System.out.println("Here");
							}
							else{
								HashSet<String> nextFirstSet = firstSet.get(put);

								if (followSet.containsKey(term)){

									HashSet<String> currFollow = followSet.get(term);

									HashSet<String> replacement = unionSets(currFollow, nextFirstSet, put);

									followSet.put(term, replacement);
								}
								else{
									HashSet<String> currSet = new HashSet<String>(nextFirstSet);
									followSet.put(term, currSet);
								}
							}							
						}			
					}

					if (rNdx+1 <= cRule.length-1 && isNullable(cRule[rNdx+1])){
						String put2;						
						if (rNdx+1 == cRule.length - 1)
							put2 = currNonTerm;
						else
							put2 = cRule[rNdx+1];

						insertFollowSet(term, put2);

					} // End if nullable. 
				}// End this rule For. 
			}// End All rules for. 
		} // End big while. 



		boolean dirty = true;

		while (dirty){
			Iterator<String> itF = followSet.keySet().iterator();
			dirty = false;

			while (itF.hasNext()){

				String currNT = itF.next();

				HashSet<String> currSet = followSet.get(currNT);
				Iterator<String> itTerm = currSet.iterator();

				while (itTerm.hasNext()){
					String currTerm = itTerm.next();

					if (isNT(currTerm)){

						HashSet<String> unionWith = followSet.get(currTerm);

						HashSet<String> newSet = unionSets(currSet, unionWith, currTerm);
						followSet.put(currNT, newSet);
						dirty = true;
						break;
					}
				}
			}
		} // End Dirty While


	}


	public void generateFirstSet(){
		Iterator<String> it = rules.keySet().iterator();

		while (it.hasNext()){
			String currNT = it.next();
			HashSet<String> currFirsts = new HashSet<String>();
			ArrayList<String[]> currRules = rules.get(currNT);

			for (int aNdx = 0; aNdx < currRules.size(); aNdx ++){

				String[] currRule = currRules.get(aNdx);

				for (String currTerm: currRule){
					if (!currTerm.equals("<epsilon>"))
						currFirsts.add(currTerm);

					if (!isNullable(currTerm))
						break;

				}
			}

			firstSet.put(currNT, currFirsts);

		} // End While

		boolean dirty = true;

		while (dirty){
			Iterator<String> itF = firstSet.keySet().iterator();
			dirty = false;

			while (itF.hasNext()){

				String currNT = itF.next();

				HashSet<String> currSet = firstSet.get(currNT);
				Iterator<String> itTerm = currSet.iterator();

				while (itTerm.hasNext()){
					String currTerm = itTerm.next();

					if (isNT(currTerm)){

						HashSet<String> unionWith = firstSet.get(currTerm);

						HashSet<String> newSet = unionSets(currSet, unionWith, currTerm);
						firstSet.put(currNT, newSet);
						dirty = true;
						break;
					}
				}
			}
		} // End Dirty While
	}

	public HashSet<String> unionSets(HashSet<String> orig, HashSet<String> add, String term){

		orig.remove(term);

		Iterator<String> it = add.iterator();

		while (it.hasNext()){
			orig.add(it.next());
		}

		return orig;

	}

	public void printFollowSet(){
		Iterator<String> it = followSet.keySet().iterator();

		while (it.hasNext()){
			String currNT = it.next();
			System.out.println(currNT);

			HashSet<String> currSet = followSet.get(currNT);
			Iterator<String> firsts = currSet.iterator();

			System.out.print("\t");
			while (firsts.hasNext()){
				String currValue = firsts.next();
				System.out.print(currValue + ":");
			}
			System.out.print("\n");


		}

	}

	public void printFirstSet(){
		Iterator<String> it = firstSet.keySet().iterator();

		while (it.hasNext()){
			String currNT = it.next();
			System.out.println(currNT);

			HashSet<String> currSet = firstSet.get(currNT);
			Iterator<String> firsts = currSet.iterator();

			System.out.print("\t");
			while (firsts.hasNext()){
				String currValue = firsts.next();
				System.out.print(currValue + ":");
			}
			System.out.print("\n");


		}

	}

	public void insertFollowSet(String term, String put)
	{
		if (!term.equals(put)){

			if (followSet.containsKey(term)){
				followSet.get(term).add(put);
			}
			else{
				HashSet<String> currSet = new HashSet<String>();
				currSet.add(put);
				followSet.put(term, currSet);
			}
		}
	}

	public void printRules(){
		Iterator<String> it = rules.keySet().iterator();

		while (it.hasNext()){

			String currNonTerm = it.next();

			System.out.println(currNonTerm);

			ArrayList<String[]> currRules = rules.get(currNonTerm);

			for(int aNdx = 0; aNdx < currRules.size(); aNdx++ ){
				String[] cRule = currRules.get(aNdx);
				System.out.print("\t");
				for (String term: cRule){
					System.out.print(term + "-");
				}
				System.out.print("\n");

			}
		}
	}

	public void generateRules() throws IOException{
		String line = null;
		BufferedReader reader = new BufferedReader(new FileReader(filename));
		boolean foundFirst = false;
		
		while ((line = reader.readLine()) != null){
			
			int divisor = line.indexOf("::=");

			String nonTerm = line.substring(0, divisor-1);
			if(!foundFirst) {
				foundFirst = true;
				firstNonTerminal = nonTerm;
			}
			String rule = line.substring(divisor+3).trim();

			String[] unionCheck = rule.split("\\|");

			for (String eachRule: unionCheck){

				String[] currRule = eachRule.trim().split(" ");

				if (rules.containsKey(nonTerm)){
					ArrayList<String[]> allRules = rules.get(nonTerm);
					allRules.add(currRule);

					rules.put(nonTerm, allRules);
				}
				else{
					ArrayList<String[]> allRules = new ArrayList<String[]>();
					allRules.add(currRule);
					rules.put(nonTerm, allRules);
				}

			}

		} // end while 

		reader.close();
	}

	public boolean isNT(String in){

		// Function to check if a token is a non terminal.

		if (in.equals("<epsilon>"))
			return false;
		
		if (in.indexOf("<") != -1)
			return true;
		else
			return false;
	}

	
	public void generateParsingTable(){
		parseTable = new HashMap<String, HashMap<String, String[]>>();
		for(String s : rules.keySet()) {
			for(String[] rule : rules.get(s)) {
				if(parseTable.get(s) == null)
					parseTable.put(s, new HashMap<String, String[]>());
				if(rule[0].equals("<epsilon>")) {
					for(String f : followSet.get(s)) {
						parseTable.get(s).put(f, new String[] {"<epsilon>"});
					}
				}
				else if(!isNT(rule[0])) {
					parseTable.get(s).put(rule[0], rule);
				} else {
					for(String f : firstSet.get(rule[0])) {
						parseTable.get(s).put(f, rule);
					}
				}

			}
		}

		/*
		 * 
		 * The logic as follows. 
		 * 
		 * Given a rule: X->YABC
		 * 
		 * If Y is a terminal, insert YABC into [X Y]
		 * If Y is a non terminal, insert YABC into [X z] where z is every value in the FIRST(Y)
		 * If X is nullable, then insert epsilon into [X q] where z is every value in the FOLLOW(X)
		 */
	}
	
	public LLParser getParser() {
		return new LLParser(parseTable, firstNonTerminal);
	}

	public boolean isNullable(String in){

		ArrayList<String[]> currRules = rules.get(in);

		if (currRules == null)
			return false;

		for (int aNdx = 0; aNdx < currRules.size(); aNdx ++){
			String[] thisRule = currRules.get(aNdx);

			for (String term: thisRule){
				if (term.equals("<epsilon>"))
					return true;
			}
		}

		return false;


	}
	
	public static void main(String args[]) throws IOException{

		String filename = "testGrammar2.txt";

		LLGenerator generator = new LLGenerator(filename);

		//generator.printRules();
		//System.out.println("**************");
		generator.printRules();
		System.out.println("**************");
		//generator.printRules();		
		generator.printFollowSet();
		System.out.println("**************");
		generator.printFirstSet();

		/*
		if (generator.isNullable("<exp-list-tail>"))
			System.out.println("Yes");
		else
			System.out.println("No");		
		for(String s : generator.parseTable.keySet()) {
			System.out.println(s);
			for(String terminal : generator.parseTable.get(s).keySet()) {
				System.out.println("\t" + terminal);
				for(String rule : generator.parseTable.get(s).get(terminal)) {
					System.out.print("\t\t" + rule);
					System.out.println();
				}
			}
		}*/

	}
}